import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.06. 汉诺塔问题
 * https://leetcode-cn.com/problems/hanota-lcci/
 */
public class Solutions_mianshi_08_06 {
    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        A.add(2);
        A.add(1);
        A.add(0);
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();

        hanota(A, B, C);
        System.out.println(C);
    }

    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        if (A.size() < 1) {
            return;
        }
        movePlate(A.size(), A, B, C);
    }

    /**
     * 递归实现模拟操作
     * 1. 将 A 中顶部的 n - 1 个盘子，通过 C，搬到 B 中
     *      此时，A 中只剩下一个盘子，B 中 n - 1 个盘子，C 空出
     * 2. A 中剩余一个盘子，将盘子搬到 C 中
     *      此时，A 空出，B 中有 n - 1 个盘子，C 中一个盘子
     * 3. 此时将 B 看作之前的 A，重复第一个步骤，即 将 B 中顶部的 n - 1 个盘子，通过 A，搬到 C 中
     * 4. 最终 A 空出，B 空出，C 中 n 个盘子
     * @param aSize A 柱子的盘子数量
     * @param A 源柱子
     * @param B 辅助柱子
     * @param C 最终柱子
     */
    public static void movePlate(int aSize, List<Integer> A, List<Integer> B,
                                 List<Integer> C) {
        if (aSize == 1) {
            // 递归终止条件，源柱子 A 上的盘子只有一个时，移动到目标柱子 C 中
            C.add(A.remove(A.size() - 1));
            return;
        }
        // 1. 递归：借助 C，将 A 柱子上 n - 1 个盘子移动到辅助柱子 B 中
        movePlate(aSize - 1, A, C, B);
        // 2. 目标柱子 C 添加源柱子 A 最底部的一个盘子，作为 C 最目标柱子最底部的盘子
        C.add(A.remove(A.size() - 1));
        // 此时，A 柱子已空，C 柱子起码有一个盘子，那么剩下的盘子全部在 B 中
        // 3. 递归：借助 A，将 B 柱子上 n - 1 个盘子全部移动到 C 中
        movePlate(aSize - 1, B, A, C);
    }
}
